\documentclass[10pt, a4paper]{article}
\input{macrostp2.tex}
\usepackage{hyperref}
\usepackage{color}
\usepackage{paralist}


%El siguiente paquete permite escribir la caratula facilmente
\usepackage{caratula}
\hypersetup{
  pdftitle={ Algoritmos III - TP2 },
  colorlinks,
  citecolor=black,
  filecolor=black,
  linkcolor=black,
  urlcolor=black 
}



\newlength{\AnchoEncabezados}\setlength{\AnchoEncabezados}{6em}
\newcommand{\EncabezadoInline}[2]{
    
    \setlength{\hangindent}{\tadAnchoEncabezados + \parindent}%
    
        \parbox{\AnchoEncabezados}{\textbf{#1}}#2%
}



\newcommand{\Encabezado}[2]{%
    \par\EncabezadoInline{#1}{#2}\par%
}

\newcommand{\funcion}[2]{\textbf{#1}{#2}\BlankLine}

%\newcommand{\myFuncion}[3]{
%	\begin{algorithm}[H][H]
%	\dontprintsemicolon
%	{\bf {#1}} {#2}\;
%	\nocaptionofalgo
%	\Indp
%	{#3}
%	\Indm
%	\BlankLine
%	\end{algorithm}
%}
   
%Datos para la caratula
\materia{Algoritmos y Estructuras de Datos 3}

%\titulo{TP II - AED3}
\titulo{TP III - AED3}

%\fecha{DDDD dd de MMMM, AAAA}

%\grupo{Grupo 14}

%\integrante{Alejandro Dan\'os}{381/10}{adp007@msn.com}
%\integrante{Clara Villalba}{695/05}{claraofvillalba@hotmail.com}
%\integrante{Cristian Gaston Lopez}{515/08}{kakoseguro@hotmail.com}
%\integrante{Nicol\'as Bratina}{444/01}{nicobratina@gmail.com}

\grupo{Grupo 2}

\integrante{Alejandro Dan\'os}{381/10}{adp007@msn.com}
\integrante{Alan Castro}{356/10}{alancastro90@gmail.com}
\integrante{Claudio Graiño}{650/10}{claudio.cuervo.17@gmail.com}
\integrante{Nicol\'as Bratina}{444/01}{nicobratina@gmail.com}
\begin{document}

 %esto construye la caratula
 \maketitle
 \tableofcontents


\newpage
\section{Introducción}
En este trabajo práctico se debe encontrar la mejor solución al problema de encontrar dos circuitos simples que cubran todos los nodos de un grafo \textit{G}, y que compartan un solo nodo \textbf{v}, tal que minimicen la suma de los pesos totales de los dos circuitos.

Dividimos el informe en 5 partes: una sección respectiva para el algoritmo exacto, el algoritmo constructivo, el algoritmo de búsqueda local y el algoritmo de la metaheurística de tabú. En cada una de ellas dividimos las subsecciones del mismo modo que lo hacíamos en los trabajos prácticos anteriores: introducción, desarrollo, pseudocódigo, demostración de la solución (no demasiado estricta) y tests.

La quinta parte sería la parte en la cual comparamos el rendimiento entre ellos para ver qué tan eficaces son en términos de tiempo y qué tan \textit{acertados} estaban con respecto a la mejor solución encontrada por el algoritmo exacto. Esto último sólo con casos chicos ya que desde un cierto \textit{n} el algoritmo exacto deja de ser viable hasta para tests. Ya para casos más grandes comparamos entre los otros algoritmos sin el exacto y por ende sin saber cuál es la solución óptima pero sí sabiendo cuál es la más acertada.

\subsection{Casos en la vida real}
Este tipo de problemas tiene relevancia en muchas áreas, no sólo de computación. Las más intuitivas son los casos en los que se deben recorrer diferentes puntos y se divide al trabajo entre dos y se debe volver al inicio sin repetir puntos y con la menor distancia recorrida posible:
\begin{compactitem}
  \item Casos más específicos serían dos camiones de basura en una ciudad relativamente chica tal que sólo se necesiten dos para recorrer la ciudad completamente dividiéndose el trabajo entre ellos. Lo mismo con dos viajantes de comercio, dos vendedores de cualquier tipo de producto, etcétera. En todos se trataría de minimizar la distancia total recorrida.
  \item Un caso menos intuitivo sería en el área de computación como en la parte de ingeniería de los chips. Si necesito que, por ejemplo, una carga eléctrica recorra una cierta cantidad de transistores pero necesito una respuesta más rápida que esperar a que recorra a todos en una pasada, por alguna razón que no parecería descabellada ya que se buscan este tipo de cosas en ingeniería, divido a los nodos en dos circuitos para mandar el mensaje por cada uno. De este modo, la respuesta llegaría antes y podría hacer algo con ella mientras espero por la segunda, la del otro circuito, por ejemplo.
 
 \item El manager de un grupo de rock debe organizar el itinerario de las ciudades que la banda debe visitar en su gira mundial. El manager quiere minimizar las distancias recorridas entre las ciudades por razones logísticas y económicas. Hay ciertas restricciones para el armado del itinerario: La banda quiere realizar tres fechas en su ciudad natal $v$ (de \textit{Vienna}), la primer función abriendo en Vienna, la segunda a mitad de la gira, y la tercera, como ultimo concierto cerrando la gira. Consideramos que 2-TSP modela correctamente este problema.\\
\end{compactitem}



\newpage
\input{exacto.tex}

\newpage
\input{constructiva.tex}

\newpage
\input{busqlocal.tex}
%\newpage
%\input{p2.tex}

\newpage
\input{tabu.tex}

\newpage
\input{tests.tex}


\end{document}


%resumen de macros:

%si el \IF no queda bien, agrego un \mbox{} (esto agrega como un espacio despues de la ultima linea)
%~: agregar espacio

%\igobs = igualdad observacional (=_obs)
%\yluego, \oluego, \impluego = eso mismo

%encierro el sub parametro entre otro par de llaves
%\tadOperacion{def?}{clave,{dicc(clave, significado)}}{bool}{}

%\tadAlinearAxiomas{cadena mas larga que hay del lado derecho}
%los ~ se usan para agregar espacio extra
